|
In graph theory, the lexicographic product or graph composition of graphs and is a graph such that * the vertex set of is the cartesian product ; and * any two vertices and are adjacent in if and only if either is adjacent with in or and is adjacent with in . If the edge relations of the two graphs are order relations, then the edge relation of their lexicographic product is the corresponding lexicographic order. The lexicographic product was first studied by . As showed, the problem of recognizing whether a graph is a lexicographic product is equivalent in complexity to the graph isomorphism problem. ==Properties== The lexicographic product is in general noncommutative: . However it satisfies a distributive law with respect to disjoint union: . In addition it satisfies an identity with respect to complementation: . The independence number of a lexicographic product may be easily calculated from that of its factors : :. The clique number of a lexicographic product is as well multiplicative: :. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Lexicographic product of graphs」の詳細全文を読む スポンサード リンク
|